
using System;
using System.Collections.Generic;
using System.IO;

namespace Ack
{
	public class HuffmanDecoder : ByteSupplier
	{
		private List<byte> _huffStream;
		private int _huffStreamPos;			// position in bit stream
		private int _expectedSymbolCount;	// expected number of symbols (divide by two to get byte count)
		private int _decodedSymbolCount;	// currently decoded number of symbols
		private byte[] _codes;				// 16-byte table of codes (formatted for easy decoding)
		private byte[] _codeMasks;			// 16-byte table of masks for the codes
		private byte[] _codeLengths;		// 16-byte table of lengths of the codes
		
		public HuffmanDecoder(List<byte> huffStream)
		{
			// Huffman bit stream.
			_huffStream = huffStream;
			
			// Decompressed block length is stored first.
			_expectedSymbolCount = 2 * (_huffStream[0] + (_huffStream[1] << 8));

			// Regenerate canonical Huffman codes and helper tables for decoding.
			CreateHuffmanDecoderTables();

			// Bit position of start of data.
			_huffStreamPos = (2+48) * 8;
			
			// No symbols decoded so far.
			_decodedSymbolCount = 0;
		}
		
		// Returns true if there are more bytes to decode.
		public bool HasMoreBytes()
		{
			return (_huffStreamPos >> 3) < _huffStream.Count && _decodedSymbolCount < _expectedSymbolCount;
		}

		// Decode one byte (if at end of stream, returns 0)
		public byte ReadByte()
		{
			byte symbolPair = 0;

			if((_decodedSymbolCount & 1) != 0)
				throw new IOException("HuffmanDecoder: Desynced stream.");
			
			for(int pairIndex = 0; pairIndex < 2; ++pairIndex)
			{
				if(!HasMoreBytes())
					break;
				
				int bytePos = _huffStreamPos >> 3;
				int fracPos = _huffStreamPos & 7;

				// Tiny sliding window of bits, built from two bytes of the input.
				byte bits;
				bits = (byte)(_huffStream[bytePos] >> fracPos);
				
				// Add contribution from second byte.
				if(bytePos+1 < _huffStream.Count)
					bits |= (byte)(_huffStream[bytePos+1] << (8-fracPos));

				// Look for the bit pattern in the code table.
				bool found = false;
				for(int i = 0; i < 16; ++i)
				{
					// Skip unused codes.
					if(_codeLengths[i] > 0)
					{
						// Mask off the code length of the code we're testing, 
						// from the input bits, and compare.
						if(_codes[i] == (bits & _codeMasks[i]))
						{
							// Write one half of an output byte using this symbol.
							if(pairIndex == 0)
							{
								symbolPair = (byte)i;
							}
							else
							{
								symbolPair |= (byte)(i << 4);
								

							//	if(_decodedSymbolCount <20)
							//		Console.WriteLine(symbolPair);								
							}
							
							// Advance sliding input window by 'codelength' nr of of bits.
							_huffStreamPos += _codeLengths[i];
							
							
							// And we found a symbol so break out.
							_decodedSymbolCount++;
							found = true;
							break;
						}
					}
				}

				if(!found)
				{
					throw new IOException("HuffmanDecoder: Failed to find code " + bits);
				}
				
			}
			
			return symbolPair;
		}

		// Generate code entry for decoding. This is LSB-first, so if the code is 1011 (length 4)
		// the generated byte is 00001101. This is the order we're reading from _huffStream later.
		public static byte GenerateCodeEntry(int currentCode, int currentCodeLength)
		{
			byte code = 0;
			for(int codebit = 1 << (currentCodeLength-1), bit = 1; 
			    codebit >= 1; 
			    codebit >>= 1, bit <<= 1)
			{
				code |= (byte)((currentCode & codebit) != 0 ? bit : 0);
			}
			return code;
		}
		
		// Generate bit mask for a code word of specified length.
		// E.g. for the code entry 00001101 this mask will be 00001111.
		public static byte GenerateMaskEntry(int codeLength)
		{
			byte mask = 0;
			for(int i = 0; i < 8; ++i)
			{
				mask |= (byte)(i < codeLength ? (1 << i) : 0);
			}
			return mask;
		}
		
		// Create tables used while decoding.
		private void CreateHuffmanDecoderTables()
		{
			_codes = new byte[16];
			_codeMasks = new byte[16];
			_codeLengths = new byte[16];			
			for(int i = 0; i < 16; ++i)
			{
				_codes[i] = _huffStream[i+2];
			}
			for(int i = 0; i < 16; ++i)
			{
				_codeMasks[i] = _huffStream[i+2+16];
			}
			for(int i = 0; i < 16; ++i)
			{
				_codeLengths[i] = _huffStream[i+2+32];
			}
			/*
			
			// Unpack the code lengths for (max) 16 symbols from these 8 header bytes. 
			byte[] codeLengths = new byte[16];
			for(int i = 0; i < 8; ++i)
			{
			  codeLengths[i*2] = (byte)(_huffStream[i+2] & 15);
			  codeLengths[i*2+1] = (byte)(_huffStream[i+2] >> 4);
			}
			
			// Now sort the tuples { symbol, codelength } on code 
			// length first, then on symbol value.
			// This mirrors what was done in the encoder.
			// Note: Slow and simple.
			byte[] sortedCodeLengths = new byte[16];
			byte[] sortedSymbols = new byte[16];
			{
				int sortPos = 0;
				int curLen = 1;
				while(sortPos<16 && curLen < 16)
				{
				  for(int i = 0; i < 16; ++i)
				  {
				    if(codeLengths[i] == curLen)
				    {
						sortedSymbols[sortPos] = (byte)i;
				      	sortedCodeLengths[sortPos++] = (byte)curLen;
				    }
				  }
				
				  curLen++;
				}
			}

			// Recreate canonical huffman codes from the length-sorted tuples.
			// Note: The output tables are in symbol order, so decoding each symbol 
			// will be an O(m) search where m is the number of USED symbols (<=16).
			// Unused symbols will have 0 in _codeLengths and _codeMasks.
			_codes = new byte[16];
			_codeMasks = new byte[16];
			_codeLengths = new byte[16];

			// Start at the shortest code length, and the code consisting of all zeroes.
			int currentCodeLength = sortedCodeLengths[0];
			int currentCode = 0;
			for(int ci = 0; ci < 16; ++ci)
			{
				// Stop generating if we reach unused codes.
				if(sortedCodeLengths[ci] == 0)
					break;

				// Generate table entries for this code.
				_codes[sortedSymbols[ci]] = GenerateCodeEntry(currentCode, currentCodeLength);
				_codeMasks[sortedSymbols[ci]] = GenerateMaskEntry(currentCodeLength);
				_codeLengths[sortedSymbols[ci]] = (byte)currentCodeLength;
			
				// Count the code up.
				currentCode++;
				
				// ..and when we need to move to a one-bit-longer code, shift 'currentCode' up by one.
				// This ensures "canonical" properties.
				if(ci < 15)
				{
					int longer = sortedCodeLengths[ci+1] - sortedCodeLengths[ci];
					currentCode <<= longer;
					currentCodeLength += longer;
				}
			}		*/
		}

	}
}
